#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N];
const int C = 1e6+10;
int tong[C];
int ans = 0;
void add(int val){
    tong[val]++;
    if(tong[val] == 1){
        ans++;
    }
}
void remove(int val){
    tong[val]--;
    if(!tong[val]){
        ans--;
    }
}
int cp[N],cv[N],cbak[N],cc;
int ql[N],qr[N],qt[N],qc;
int qidx[N];
int rans[N];
int bl[N];
bool cmp(int x,int y){
    return bl[ql[x]] < bl[ql[y]] || 
            bl[ql[x]] == bl[ql[y]] && bl[qr[x]] < bl[qr[y]] || 
            bl[ql[x]] == bl[ql[y]] && bl[qr[x]] == bl[qr[y]] && qt[x] < qt[y];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
    }   
    int block = pow(n,2.0/3);
    int tot = n/block + (n % block != 0);
    for(int i = 1;i<=m;i++){
        char c;
        cin>>c;
        if(c == 'Q'){
            int now = ++qc;
            cin>>ql[now];
            cin>>qr[now];
            qt[now] = cc;
            qidx[now] = now;
        }else{
            int now = ++cc;
            cin>>cp[now]>>cv[now];
        }
    }
    for(int i = 1;i<=tot;i++){
        int lp = (i - 1)*block + 1,rp = min(i*block,n);
        for(int j = lp;j <= rp;j++){
            bl[j] = i;
        }
    }
    sort(qidx + 1,qidx + 1 + qc,cmp);
    int cl = 1,cr = 0,ct = 0;
    for(int p = 1;p <= qc;p++){
        int l = ql[qidx[p]],r = qr[qidx[p]],t = qt[qidx[p]];
        while(cr < r){
            cr++;
            add(a[cr]);
        }
        while(cr > r){
            remove(a[cr]);
            cr--;
        }
        while(cl > l){
            cl--;
            add(a[cl]);
        }
        while(cl < l){
            remove(a[cl]);
            cl++;
        }
        while(ct < t){
            ct++;
            cbak[ct] = a[cp[ct]];
            a[cp[ct]] = cv[ct];
            if(l <= cp[ct] && cp[ct] <= r){
                remove(cbak[ct]);
                add(cv[ct]);
            }
        }
        while(ct > t){
            a[cp[ct]] = cbak[ct];
            if(l <= cp[ct] && cp[ct] <= r){
                remove(cv[ct]);
                add(cbak[ct]);
            }
            ct--;
        }
        rans[qidx[p]] = ans;
    }
    for(int i = 1;i<=qc;i++){
        cout<<rans[i]<<'\n';
    }
    return 0;
}